/**
 * 分三种情况，1.头结点多一条边，有环。2.子节点多一条边，有环。3.子节点多一条边，无环
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantDirectedConnection = function (edges) {
    // 首先构建并查集
    let len = edges.length,
        father = new Array(len + 1).fill(0).map((val, index) => index);

    function join(a, b) {
        a = find(a);
        b = find(b);
        if (a === b) return
        father[b] = a
    }

    function find(a) {
        return a === father[a] ? a : father[a] = find(father[a])
    }

    function isSame(a, b) {
        a = find(a);
        b = find(b);
        return a === b
    }

    // 记录是否有多父节点的节点
    let sonMap = new Map(),
        firstSameSonIndex = null,
        secondSameSonIndex = null;
    for (let i = 0; i < edges.length; i++) {
        if (sonMap.has(edges[i][1])) {
            secondSameSonIndex = i
            firstSameSonIndex = sonMap.get(edges[i][1])
        } else {
            sonMap.set(edges[i][1], i)
        }
    }

    if (firstSameSonIndex === null) {
        // 无多父节点的节点，情况1，去除最后一条构成环的边
        for (let [x, y] of edges) {
            if (isSame(x, y)) {
                return [x, y]
            } else {
                join(x, y)
            }
        }
    } else {
        for (let i = 0; i < edges.length; i++) {
            if (i === firstSameSonIndex || i === secondSameSonIndex) continue
            join(edges[i][0], edges[i][1])
        }
        // 如果有环，肯定只有一条边构成了环，如果是前面那条边，删除
        if (isSame(edges[firstSameSonIndex][0], edges[firstSameSonIndex][1])) {
            return [edges[firstSameSonIndex][0], edges[firstSameSonIndex][1]]
        } else {
            // 如果有环，肯定只有一条边构成了环，如果是后面那条边，删除
            // 如果没有环，删除后面那条边
            return [edges[secondSameSonIndex][0], edges[secondSameSonIndex][1]]
        }
    }




};